/**
 *
 * @author Anastasiya
 *
 * Ozawa algorithm realization
 *
 */

#pragma once
#include "algorithm.h"
#include <ogdf/basic/Graph.h>
#include <ogdf/basic/NodeArray.h>
#include <ogdf/internal/planarity/PlanarSubgraphPQTree.h>
#include <ogdf/internal/planarity/PlanarPQTree.h>
#include <cstring>
#include <map>

using namespace ogdf;
using namespace std;

typedef PlanarLeafKey<whaInfo*> PlanarPQTreeLeaf;
typedef SListPure<PlanarPQTreeLeaf*> PQTreeLeafs;

class OzawaAlgorithm:public Algorithm{
public: OzawaAlgorithm();
		~OzawaAlgorithm();
		TestResult* execute(string resultPath, string file);
		string getName();
private: string name;
		 Graph* readGraph(string filename);
		 NodeArray<int>* computeStNumbering(Graph* g);
		 void computePQTreeLeaves(Graph* g, NodeArray<int>* stNumbering, map<node, PQTreeLeafs*>* leafsMap, Array<node>* stNumberedNodes);
		 PQTreeLeafs* computePQTreeLeaves(node* n, NodeArray<int>* stNumbering);
		 void computeLeavesForReduce(Graph* g, map<node, PQTreeLeafs*>* treeLeavesMap, map<node, PQTreeLeafs*>* reduceLeavesMap);
		 void deleteEdges(Graph* g, SList<PQLeafKey<edge, whaInfo*, bool>*>* edgesToDelete);
		 string getFileName(string file);

		 static const int ST_NUMBERING_FAILED;

		 static const string PROCESS_MESSAGE_READING_GRAPH;
		 static const string PROCESS_MESSAGE_MAKING_ST_NUMBERING;
		 static const string PROCESS_MESSAGE_COMPUTING_LEAFS;
		 static const string PROCESS_MESSAGE_COMPUTING_REDUCE_LEAFS;
		 static const string PROCESS_MESSAGE_COMPUTING_PQ_TREES;
		 static const string PROCESS_MESSAGE_INITIALIZING_FIRST_TREE;
		 static const string PROCESS_MESSAGE_REDUCING_TREE;
		 static const string PROCESS_MESSAGE_DELETING_EDGES;
		 static const string PROCESS_MESSAGE_WRITING_RESULT;

		 static const string PROCESS_ERROR_NO_SUCH_FILE;
		 static const string PROCESS_ERROR_MUST_CONTAINT_MORE_THEN_3_NODES;
		 static const string PROCESS_ERROR_MUST_BE_SIMPLE;
		 static const string PROCESS_ERROR_ST_NUMBERING;
		 static const string PROCESS_ERROR_UNKNOWN_ERROR;
		 static const string PROCESS_ERROR_REDUCING_FAILED;
		 static const string PROCESS_ERROR_EXCEPTION;

		 static const string ALGORITHM_NAME;
};